package com.graph;

import java.util.*;

public class Solution433 {
    int res = Integer.MAX_VALUE;

    public int minMutation(String S, String T, String[] bank) {
        boolean[] used = new boolean[bank.length];
        backtracking(S, T, bank, used, 0);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public void backtracking(String s, String t, String[] bank, boolean[] used, int count) {
        if (count > res) return;
        if (s.equals(t)) {
            res = Math.min(res, count);
        }
        for (int i = 0; i < bank.length; i++) {
            if (used[i]) continue;
            int dif = 0;
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) != bank[i].charAt(j)) dif++;
            }
            if (dif == 1) {
                used[i] = true;
                backtracking(bank[i], t, bank, used, count + 1);
                used[i] = false;
            }
        }
    }
}